package com.example.commonlib.commonutil;

import java.util.Random;

/**
 * Created by yyairmarkyy on 2017/9/28.
 */

public class SortUtil {

    /**
     * 选择排序法 O(n^2)
     * @param a
     * @return
     */
    public static int[] selectSort(int[] a){
        int lenth = a.length;
        for (int i = 0; i<lenth; i++){
            int minIndex = i;
            for (int j = i+1;j<lenth;j++){
                if (a[j] < a[minIndex])
                    minIndex = j;
            }

            swap(a,i,minIndex);
        }
        return a;
    }


    /**
     * 插入排序(base)
     * @param a
     * @return
     */
    public static int[] insertSort(int[] a){
        for (int i = 1;i<a.length;i++){

            for (int j = i;j>0;j--){
                if (a[j-1] >= a[j]){
                    swap(a,j-1,j);
                }else{
                    break;
                }
            }
        }

        return a;
    }

    /**
     * 插入排序(optimization)
     * @param a
     * @return
     */
    public static long[] insertSortOpt(long[] a){
        for (int i = 1;i<a.length;i++){
            long insertValue = a[i];
            int j;
            for (j = i;j>0 && a[j-1] >= insertValue;j--) {
                a[j] = a[j - 1];
            }
            a[j] = insertValue;
        }

        return a;
    }


    /**
     * 冒泡排序
     * @param a
     * @return
     */
    public static int[] BubbleSort(int[] a){
        for (int i = a.length-1;i>0;i--){
            for (int j = 0;j<i;j++){
                if (a[j] > a[j+1]){
                    swap(a,j,j+1);
                }
            }
        }
        return a;
    }

    /**
     * 希尔排序
     * @return
     */
    public static int[] shellSort(int[] a) {
        int n = a.length;
        while (true){
            n = n/2;
            for (int i=1;i<a.length;i+=n){
                int insertValue = a[i];
                int j;
                for (j=i;j>0 && a[j-1] >= insertValue;j--){
                    a[j] = a[j-1];
                }
                a[j] = insertValue;
            }
            if (n == 1)
                break;

        }

        return a;
    }

    /**
     * 归并排序
     * @param a
     * @return
     */
    public static int[] mergeSort(int[] a){

        mergeSort(a,0,a.length-1);

        return a;

    }


    /**
     * 归并排序中用来分段
     * @param a
     * @param l
     * @param r
     */
    private static void mergeSort(int[] a,int l,int r){
        if (l>=r)
            return;

        int n = (l+r)/2;
        mergeSort(a,l,n);
        mergeSort(a,n+1,r);
        merge(a,l,n,r);
    }


    /**
     * 把每段进行排序合并（最小段为2个元素）
     * @param a
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] a,int l,int mid,int r){

        int arr[] = new int[r-l+1];
        for (int i = l;i<r+1;i++){
            arr[i-l] = a[i];
        }

        int i = l;
        int j = mid+1;
        int k ;
        for (k = l;k<r+1;k++){

            if (i>mid){
                a[k] = arr[j-l];
                j++;
            }else if (j>r){
                a[k] = arr[i-l];
                i++;
            }else if (arr[i-l] > arr[j-l]){
                a[k] = arr[j-l];
                j++;
            }else {
                a[k] = arr[i-l];
                i++;
            }
        }

    }




    /**
     * 生成相对有序的无序数组
     * @param n 数组大小
     * @param swapTimes 需要打乱顺序的次数
     * @return
     */
    public static int[] generateNearlyRandomArray(int n,int swapTimes){
        int[] arr = new int[n];
        for (int i = 0 ; i<n; i++){
            arr[i] = i;
        }
        for (int j = 0; j<swapTimes; j++){
            int r1 = new Random().nextInt(n);
            int r2 = new Random().nextInt(n);
            swap(arr,r1,r2);
        }
//        printArray("generateNearlyRandomArray",arr);
        return arr;
    }


    /**
     * 生成指定区间的无序数组
     * @param n 数组个数
     * @param left 做区间（闭区间）
     * @param right 右区间（闭区间）
     * @return
     */
    public static int[] generateRandomArray(int n,int left,int right){
        int[] arr = new int[n];
        for (int i = 0; i<n; i++){
            int ran = new Random().nextInt(right-left+1)+left;
            arr[i] = ran;
        }

        return arr;
    }


    /**
     * 交换数组值
     * @param a
     * @param indexA
     * @param indexB
     */
    public static void swap(int[] a,int indexA,int indexB){

        if (indexA == indexB)
            return;

        int temp = a[indexB];
        a[indexB] = a[indexA];
        a[indexA] = temp;
    }



}
